Attributed to the least-cost stream

https://gyazo.com/4b7d4a231225f9f2363bf0e692829b53

Organize notation and draw the flow of various problems.

itemized discussion

https://gyazo.com/38dcd4abb0b8f661eb30039f293a802c

Xi stones are placed in three locations.

Assign up to one of these to an unspecified number of squares.

The problem condition is infinite number of pieces, but realistically, a number about the sum of Xi is sufficient.

Cost Cij is the distance from the place where it is located to the destination

https://gyazo.com/c243561fb3069ff0f7a2c41046325ef2

https://gyazo.com/11af29d8073e126040a8d77a4f22b2d8

Assign N locations for M objects in each of the three rounds

At this time, the reward Rij is obtained

However, the cost Djk depends on how many k were finally assigned to location j

This cost is progressive.

So it can be expressed using Cjk=Djk-Dj(k-1)

Because they are chosen from the cheapest

https://gyazo.com/eaaba4778f81bf4f4751b1e923ffae74

Up to K in the same row

= Select up to K from N locations

It is important to note that not just K pieces

Acknowledge the choice not to choose by creating a side path.

The squares correspond to the edges of a bipartite graph.

https://gyazo.com/92ae403683bc716bc08c1a73ec2e8528

Choose the one with the smallest cost among those with the largest rewards to be obtained.

The number of choices is M, the number of pieces chosen L=min(N, M)

Rewards are used to construct the graph instead of putting them on the edges.

Sort in order of reward Rj, and select the remaining L-A pieces from the B pieces with the same score as the Lth piece, with A as the number of pieces to be selected with a definite score higher than the Lth piece.

undirected graph

Shortest path from vertex 1 to N and back to 1

Can go through the same side twice.

1st cost ci, 2nd cost di, di>=ci

https://gyazo.com/0ab440e908ffd90d188962117aa3ec02

Flow rate 2

Why is this okay?

https://gyazo.com/671dddb208ffc7a1f3033431de840421

If you're going through an edge only once, you can go through in the opposite direction for the same cost.

When you're going through it twice, the opposite side is gone, so it costs d

Divide the cost by 2 through flow rate 2 to get what you want to ask for.

relevance

Comes down to the shortest path problem.

---